As an increasing number of applications and services are being made available over networks such as the Internet, an increasing number of content, application, and/or service providers are turning to technologies such as cloud computing. Cloud computing, in general, is an approach to providing access to electronic resources through services, such as Web services, where the hardware and/or software used to support those services is dynamically scalable to meet the needs of the services at any given time. A user or customer typically will rent, lease, or otherwise pay for access to resources through the cloud, and thus does not have to purchase and maintain the hardware and/or software needed.
Such access comes with some risk for customers, as the customers are turning over control of access to their data. In order to prevent this data from being accessed by an undesired party, many resource providers utilize encryption such that even if the data is obtained it will be difficult for the obtaining party to decrypt the data. In order to improve security, these keys are often rotated such that if one of the keys is obtained by an undesired party, that key will be useful only for a limited period of time. Unfortunately, for large, distributed systems it can be difficult to frequently rotate keys, particularly where the data encrypted under those keys has to be transmitted, decrypted, and re-encrypted each time a key is updated.